Allocation of jobs and identical resources with two pooling centers

We examine the resource allocation problem of partitioning identical servers into two parallel pooling centers, and simultaneously assigning job types to pooling centers. Each job type has a distinct Poisson arrival rate and a distinct holding cost per unit time. Each pooling center becomes a queueing system with an exponential service time distribution. The goal is to minimize the total holding cost. The problem is shown to be polynomial if a job type can be divided between the pooling centers, and NP-hard if dividing job types is not possible. When there are two servers and jobs cannot be divided, we demonstrate that the two pooling center configuration is rarely optimal. A heuristic which checks the single pooling center has an upper bound on the relative error of 4/3. The heuristic is extended for the multiple server problem, where relative error is bounded above by the number of servers.      

Allocating electricity transmission costs through tracing: a game-theoretic rationale

Tracing is a method of assigning flows in an electricity network to particular generators and loads, assuming perfect mixing at each node. It can be used to assign costs to transmission users. We show that the resulting allocation is equal to the Shapley value of an equivalent co-operative game.     

基于MPEG-4的视频流式传输系统及动态带宽分配方法

提出了一个基于MPEG 4精细可分级编码技术的视频流式传输系统。介绍了系统中主要模块的作用,并重点研究了速率控制模块。速率控制模块采用了适合视频流式传输的动态带宽分配方法。它可以根据实时的网络通道波动状况来动态调整滑动参数,以适应网络波动和高效地利用网络的有限资源。实验结果表明,动态带宽分配方法在动态带宽波动条件下不仅可以使相邻帧间的视频质量更加平滑,而且可以大大提高解码视频图像的总体质量,也就是说可同时改善解码视频的主客观性能。     

Analysis of a Duopoly Supply Chain and its Application in Electricity Spot Markets

This paper studies a supply chain consisting of two suppliers and one retailer in a spot market, where the retailer uses the newsvendor solution as its purchase policy, and suppliers compete for the retailer’s purchase. Since each supplier’s bidding strategy affects the other’s profit, a game theory approach is used to identify optimal bidding strategies. We prove the existence and uniqueness of a Nash solution. It is also shown that the competition between the supplier leads to a lower market clearing price, and as a result, the retailer benefits from it. Finally, we demonstrate the applicability of the obtained results by deriving optimal bidding strategies for power generator plants in the deregulated California energy market. Supported in part by RGC (Hong Kong) Competitive Earmarked Research Grants (CUHK4167/04E and CUHK4239/03E), a Distinguished Young Investigator Grant from the National Natural Sciences Foundation of China, and a grant from Hundred Talents Program of the Chinese Academy of Sciences.     

Compensatory transfers in two-player decision problems

This paper presents an axiomatic characterization of a family of solutions to two-player quasi-linear social choice problems. In these problems the players select a single action from a set available to them. They may also transfer money between themselves.The solutions form a one-parameter family, where the parameter is a non-negative number, t.The solutions can be interpreted as follows: Any efficient action can be selected. Based on this action, compute for each player a “best claim for compensation”. A claim for compensation is the difference between the value of an alternative action and the selected efficient action, minus a penalty proportional to the extent to which the alternative action is inefficient. The coefficient of proportionality of this penalty is t. The best claim for compensation for a player is the maximum of this computed claim over all possible alternative actions. The solution, at the parameter value t, is to implement the chosen efficient action and make a monetary transfer equal to the average of these two best claims. The characterization relies on three main axioms. The paper presents and justifies these axioms and compares them to related conditions used in other bargaining contexts. In Nash Bargaining Theory, the axioms analogous to these three are in conflict with each other. In contrast, in the quasi-linear social choice setting of this paper, all three conditions can be satisfied simultaneously.This work was supported by the Division of Research at the Harvard Business School. Thanks are due to the Cowles Foundation for Research in Economics at Yale University for its kind hospitality during the Spring of 2002. I have received helpful advice and comments from Youngsub Chun, Ehud Kalai, Herve Moulin, Al Roth, Ilya Segal, Adam Szeidl, Richard Zeckhauser, and other members of the Theory Seminars at Harvard, MIT, Princeton, Rice and Northwestern.     

Cyclic networks with general blocking and starvation

We introducegeneral starvation and consider cyclic networks withgeneral blocking and starvation (GBS). The mechanism of general blocking allows the server to process a limited number of jobs when the buffer downstream is full, and that of general starvation allows the server to perform a limited number of services in anticipation of jobs that are yet to arrive. The two main goals of this paper are to investigate how the throughput of cyclic GBS networks is affected by varying (1) the total number of jobsJ, and (2) the buffer allocationk=(k₁..., k_m) subject to a fixed total buffer capacityK=k ₁ +... + k_m. In particular, we obtain sufficient conditions for the throughput to be symmetric inJ and to be maximized whenJ=K/2. We also show that the equal buffer allocation is optimal under the two regimes of light or heavy usage. In order to establish these results, we obtain several intermediate structural properties of the throughput, using duality, reversibility, and concavity, which are of independent interest.Research supported in part by NSF Grant No. ECS-8919818.     

Solving multiple-objective problems in the objective space

Projection and relaxation techniques are employed to decompose a multiobjective problem into a two-level structure. The basic manipulation consists in projecting the decision variables onto the space of the implicit tradeoffs, allowing the definition of a relaxed multiobjective master problem directly in the objective space. An additional subproblem tests the feasibility of the solution encountered by the relaxed problem. Some properties of the relaxed problem (linearity, small number of variables, etc.) render its solution efficient by a number of methods. Representatives of two different classes of multiobjective methods [the Geoffrion, Dyer, Feinberg (GDF) method and the fuzzy method of Baptistella and Ollero] are implemented and applied within this context to a water resources allocation problem. The results attest the computational viability of the overall procedure and its usefulness for the solution of multiobjective problems.This work was partially sponsored by grants from CNP_q and FAPESP, Brazil. The authors are indebted to the anonymous reviewers for their valuable comments.     

Tuning Garwick's algorithm for repacking sequential storage

Garwick's algorithm, for repacking LIFO lists stored in a contiguous block of memory, bases the allocation of remaining space upon both sharing and previous stack growth. A system whereby the weight applied to each method can be adjusted according to the current behavior of the stacks is discussed.We also investigate the problem of determining during memory repacking that the memory is used to saturation and the driving program should therefore be aborted. The tuning parameters studied here seem to offer no new grasp on this problem.     

A note on weighted buddy systems for dynamic storage allocation

In this paper we first show that the Shen and Peterson System [1] is a combination of two Fibonacci buddy systems [2, 3]. Then we present a generalized Shen and Peterson system. The generalized system has more flexibility in the generation of fixed size blocks. For the generalized system, the algorithm for the determination of the buddy of any released block is easier than that of the Shen and Peterson system.     

A tabu search procedure for multicommodity location/allocation with balancing requirements

We propose a tabu search heuristic for the location/allocation problem with balancing requirements. This problem typically arises in the context of the medium term management of a fleet of containers of multiple types, where container depots have to be selected, the assignment of customers to depots has to be established for each type of container, and the interdepot container traffic has to be planned to account for differences in supplies and demands in various zones of the geographical territory served by a container shipping company. It is modeled as a mixed integer program, which combines zero-one location variables and a multicommodity network flow structure. Extensive computational results on a set of benchmark problems and comparisons with an efficient dual ascent procedure are reported. These show that tabu search is a competitive approach for this class of problems.